/**

   Heap.c
   ======

   Heap data structure

**/


/**

   Includes
   --------

   - stdlib.h    : mallo, free
   - chunksrv.h  : chunkserver management
   - heap.h      : Self header

**/

#include <stdlib.h>
#include "chunksrv.h"
#include "heap.h"



/**

   Function: struct heap* heap_create(int max, int (*compare)(struct heap*,struct heap*))
   --------------------------------------------------------------------------------------

   Create a heap of `max` elements allowed

**/


struct heap* heap_create(unsigned int max, int (*compare)(struct chunksrv*,struct chunksrv*))
{
  struct heap* heap;
 
  if ( (!max) || (compare == NULL) )
    {
      return NULL;
    }

  /* Heap allocation */
  heap = (struct heap*)malloc(sizeof(struct heap));
  if (heap == NULL)
    {
      return NULL;
    }

  /* Items array */
  heap->items = (struct chunksrv**)malloc(max*sizeof(struct chunksrv*));
  if (heap->items == NULL)
    {
      free(heap);
      return NULL;
    }

  /* Fields */
  heap->n = 0;
  heap->max = max;
  heap->compare = compare;

  return heap;

}


/**

   Function: void heap_delete(struct heap* heap)
   ---------------------------------------------

   Delete a heap by releasing its resources

**/

void heap_delete(struct heap* heap)
{
  unsigned int i;

  for(i=0;i<heap->n;i++)
    {
      heap->items[i] = NULL;
    }

  free(heap->items);
  free(heap);

  return;

}


/**

   Function: unsigned int heap_parent(unsigned int n)
   --------------------------------------------------

   Return parent index of child located at index `n` in the items array.

**/

unsigned int heap_parent(unsigned int n)
{
  if (n)
    {
      return ((unsigned int)(n-1)/2);
    }

  return 0;
}


/**

   Function: unsigned int heap_child(unsigned int n)
   -------------------------------------------------

   Return left most child index of parent located at index `n` in the items array.

**/

unsigned int heap_child(unsigned int n)
{
  return (2*n+1);
}



/**

   Function: void heap_swap(struct heap* h, unsigned int i, unsigned j)
   --------------------------------------------------------------------

   Swap items indexed by  `i` and `j` in `h` items array

**/

void heap_swap(struct heap* h, unsigned int i, unsigned j)
{
  /* XOR swapping */
  if (h->items[i] != h->items[j])
    {
      h->items[i] = (struct chunksrv*)( (unsigned int)h->items[i] ^ (unsigned int)h->items[j] );
      h->items[j] = (struct chunksrv*)( (unsigned int)h->items[i] ^ (unsigned int)h->items[j] );
      h->items[i] = (struct chunksrv*)( (unsigned int)h->items[i] ^ (unsigned int)h->items[j] );
    }

  return;

}


/**

   Function: void heap_bubble_up(struct heap* h, unsigned int i)
   -------------------------------------------------------------

   Bubble an item up the heap

**/


void heap_bubble_up(struct heap* h, unsigned int i)
{
  if (i)
    {
      if ( h->compare(h->items[heap_parent(i)],h->items[i]) > 0 )
	{
	  heap_swap(h,heap_parent(i),i);
	  heap_bubble_up(h,heap_parent(i));
	}
    }

  return;

}


/**

   Function: void heap_bubble_down(struct heap* h, unsigned int i)
   ---------------------------------------------------------------

   Bubble an item down the heap

**/


void heap_bubble_down(struct heap* h, unsigned int i)
{
  unsigned k,child,min_index;

  /* Get leftmost child */
  child = heap_child(i);
  
  /* Set min_index to i */
  min_index = i;

  /* Get minimum index among i and its child */
  for(k=0;k<2;k++)
    {
      if ( (child+k) < h->n)
	{
	  if ( h->compare(h->items[min_index],h->items[child+k]) > 0 )
	    {
	      min_index = child+k;
	    }
	}
    }

  /* Swap if `i` is not the min, and bubble down  */
  if (min_index != i)
    {
      heap_swap(h,i,min_index);
      heap_bubble_down(h,min_index);
    }
  
  return;
}




/**

   Function: int heap_insert(struct heap* heap, struct chunksrv* cs)
   -----------------------------------------------------------------

   Insert `cs` in `heap`

**/


int heap_insert(struct heap* heap, struct chunksrv* cs)
{
  if ( (heap->n+1 > heap->max) || ( cs == NULL) )
    {
      return EXIT_FAILURE;
    }
  
  heap->items[heap->n] = cs;
  heap_bubble_up(heap,heap->n);
  heap->n++;
  
  return EXIT_SUCCESS;

}



/**

   Function: struct chunksrv* heap_extract(struct heap* heap)
   ----------------------------------------------------------

   Extract heap root

**/


struct chunksrv* heap_extract(struct heap* heap)
{
  struct chunksrv* cs;

  if (!heap->n)
    {
      return NULL;
    }

  /* Get root */
  cs = heap->items[0];

  /* Set last item as root and bubble down */
  heap->items[0] = heap->items[heap->n-1];
  heap->items[heap->n-1] = NULL;
  heap->n--;
  heap_bubble_down(heap,0);
  
  return cs;
}


/**

   Function: int heap_remove(struct heap* heap, struct chunksrv* cs)
   -----------------------------------------------------------------

   Remove `cs` from heap

**/


int heap_remove(struct heap* heap, struct chunksrv* cs)
{
  unsigned int i;

  if (!heap->n)
    {
      return EXIT_FAILURE;

    }

  /* get `cs` index */
  for(i=0;( (i<heap->n)&&(heap->items[i]!=cs) );i++)
    {}
  
  /* Return if not found */
  if (i == heap->n)
    {
      return EXIT_FAILURE;
    }

  /* Place last item at index and bubble down */
  heap->items[i] =  heap->items[heap->n-1];
  heap->items[heap->n-1] = NULL;
  heap->n--;
  heap_bubble_down(heap,i);
  
  return EXIT_SUCCESS;

}
